package array

import (
	"fmt"
	"gitee.com/kklt1996/data-structure/common"
)

/*
 基于切片实现动态数组,使用切片本身的扩容策略
 size 表示当前有效存储的元素的数量
 因为Array是结构体，所以默认是值传递的,不会像内建结构slice一样默认传递指针的值
*/
type SliceArray []interface{}

/*
	get size of SliceArray
*/
func (array *SliceArray) Size() int {
	return len(*array)
}

/*
	数组是否为空
*/
func (array *SliceArray) IsEmpty() bool {
	return len(*array) == 0
}

/*
	add item into SliceArray
*/
func (array *SliceArray) Add(index int, item ...interface{}) {
	size := array.Size()
	// 修正要插入的index
	if index < 0 {
		index = 0
	} else if index > size {
		index = size
	}

	// 在最后一个元素后添加元素
	if index == size {
		*array = append(*array, item...)
		// 在第一个元素前插入元素
	} else if index == 0 {
		*array = append(item, *array...)
	} else {
		// 在第二个和最后一个元素之间插入元素
		head := (*array)[0:index]
		tail := (*array)[index:]
		*array = append(append(head, item...), tail...)
	}
}

/*
	在元素插入元素
*/
func (array *SliceArray) AddFirst(item ...interface{}) {
	array.Add(0, item...)
}

/*
	在元素尾部插入元素
*/
func (array *SliceArray) AddLast(item ...interface{}) {
	array.Add(array.Size(), item...)
}

/*
	delete item of SliceArray
	需要注意的是[]运算符的优先级高于*
*/
func (array *SliceArray) Remove(index int) (interface{}, error) {
	var deleteElement interface{} = nil
	size := array.Size()
	// 删除不在size范围内的元素
	if index > size-1 || index < 0 {
		return deleteElement, common.IndexError{}
		// 删除最后一个元素
	} else if index == size-1 {
		deleteElement = (*array)[index]
		*array = (*array)[:size-1]
		// 删除第一个元素
	} else if index == 0 {
		deleteElement = (*array)[index]
		*array = (*array)[1:]
		// 删除第一个和最后一个元素之外的某一个元素
	} else {
		deleteElement = (*array)[index]
		*array = append((*array)[0:index], (*array)[index+1:]...)
	}

	// 查看是否需要缩容
	array.resize()
	return deleteElement, nil
}

/*
	删除第一个元素
*/
func (array *SliceArray) RemoveFirst() (interface{}, error) {
	return array.Remove(0)
}

/*
	删除最后一个元素
*/
func (array *SliceArray) RemoveLast() (interface{}, error) {
	return array.Remove(array.Size() - 1)
}

/*
	删除某一个元素值,用一个新的动态数组来接收结果
*/
func (array *SliceArray) RemoveAllElement(value interface{}) int {
	return array.RemoveIfMatch(func(item interface{}) bool {
		return item == value
	})
}

/*
	删除某一个元素的第一个index
*/
func (array *SliceArray) RemoveElement(value interface{}) {
	index := array.FindFirst(value)
	if index != -1 {
		_, _ = array.Remove(index)
	}
}

/*
	按照条件删除元素
	返回删除元素的个数
*/
func (array *SliceArray) RemoveIfMatch(matchFunc func(interface{}) bool) int {
	if array.IsEmpty() {
		return 0
	}
	// 预先创建一个足够大小的容量
	resultArray := make([]interface{}, 0, array.Size()*2-1)
	// 保存剩余的元素
	for _, v := range *array {
		if !matchFunc(v) {
			resultArray = append(resultArray, v)
		}
	}
	removeNum := array.Size() - len(resultArray)
	*array = resultArray
	// 查看是否需要缩容
	array.resize()
	// 返回删除元素的个数
	return removeNum
}

/*
	修改数组中的元素
	范围是 [0,len()-1]
*/
func (array *SliceArray) Set(index int, value interface{}) {
	if index > len(*array)-1 || index < 0 {
		return
	}
	(*array)[index] = value
}

/*
   查询数组中的元素
   范围是 [0,len()-1]
*/
func (array *SliceArray) Get(index int) (interface{}, error) {
	if index <= len(*array)-1 && index >= 0 {
		return (*array)[index], nil
	} else {
		return nil, common.IndexError{}
	}
}

/*
	获取第一个元素
*/
func (array *SliceArray) GetFirst() (interface{}, error) {
	return array.Get(0)
}

/*
	获取最后一个元素
*/
func (array *SliceArray) GetLast() (interface{}, error) {
	return array.Get(len(*array) - 1)
}

/*
	查看动态数据中是否包含某个元素
*/
func (array *SliceArray) Contains(value interface{}) bool {
	for _, v := range *array {
		if v == value {
			return true
		}
	}
	return false
}

/*
	查看某个元素的第一个索引
*/
func (array *SliceArray) FindFirst(value interface{}) int {
	for i, v := range *array {
		if v == value {
			return i
		}
	}
	return -1
}

/*
	查看某一个元素的最后一个索引
*/
func (array *SliceArray) FindLast(value interface{}) int {
	lastIndex := -1
	for i, v := range *array {
		if v == value {
			lastIndex = i
		}
	}
	return lastIndex
}

/*
	可以删除和设置节点值的迭代器
*/
func (array *SliceArray) Iterator(iteratorFunc func(iterator common.Iterator) bool) {
	arrayIterator := &SliceArrayIterator{sliceArray: array}
	var iterator common.Iterator = arrayIterator
	for i := 0; i < array.Size(); {
		arrayIterator.index = i
		arrayIterator.removeFlag = false
		if iteratorFunc(iterator) {
			break
		} else {
			// 没有删除元素的话需要i++,删除的话删除的时候第i个元素已经变成了下一个元素所以不用i++
			if !iterator.(*SliceArrayIterator).removeFlag {
				// 获取下一个要判断是否删除的节点
				i++
			}
		}
	}
}

/*
	转化为slice
*/
func (array *SliceArray) ToSlice() []interface{} {
	return *array
}

func (array *SliceArray) String() string {
	res := fmt.Sprintf("SliceArray: size = %d , capacity = %d ", array.Size(), cap(*array))
	res += "["
	for i := 0; i < array.Size(); i++ {
		item, _ := array.Get(i)
		res += fmt.Sprintf("%v", item)
		if i != array.Size()-1 {
			res += ", "
		}
	}
	res += "]"
	return res
}

/*
	手动缩容
*/
func (array *SliceArray) resize() {
	// 当前元素个数小于等于容量的1/4的时候进行缩容操作,缩容为当前容量的1/2
	if cap(*array)/4 >= array.Size() && cap(*array)/2 != 0 {
		// 拷贝原数组
		arr := CreateSliceArray(array.Size(), cap(*array)/2)
		for i, v := range *array {
			(*arr)[i] = v
		}
		*array = *arr
	}
}

/*
	sliceArray迭代器,用于再遍历的过程中删除元素和修改元素
*/
type SliceArrayIterator struct {
	sliceArray *SliceArray

	index int

	removeFlag bool
}

/*
	删除节点
*/
func (iterator *SliceArrayIterator) Remove() {
	if iterator.removeFlag {
		return
	}
	_, _ = iterator.sliceArray.Remove(iterator.index)
	// 标记标识删除了元素
	iterator.removeFlag = true
}

/*
	修改节点的值
*/
func (iterator *SliceArrayIterator) Set(value interface{}) error {
	if iterator.removeFlag {
		return common.OperatorNotUseful{}
	}
	(*iterator.sliceArray)[iterator.index] = value
	return nil
}

/*
	获取value
*/
func (iterator *SliceArrayIterator) Get() (interface{}, error) {
	if iterator.removeFlag {
		return nil, common.OperatorNotUseful{}
	}
	return (*iterator.sliceArray)[iterator.index], nil
}
